Malarz

Limit pamięci: 256 MB

Wybierz pracę, którą kochasz,
a nie przepracujesz ani jednego dnia więcej w Twoim życiu.

Bitocy jest malarzem. Ponieważ jednak nie mógł znaleźć sobie zatrudnienia, swoją pasję realizuje jako konserwator powierzchni płaskich.

Pracuje w dziale malowania przejść dla pieszych. Podczas każdego ze zleceń głęboko kontempluje każdy fragment swojego nowego dzieła. Czasami gdzieniegdzie dokonuje poprawek. Ponieważ jednak drogi stają się coraz szersze poprosił Cię o pomoc.
Maszyna, którą pracuje Bitocy działa w dość szczególny sposób: na początek całą jezdnię maluje się na biało (aby obszar roboczy przypominał płutno). Następnie Bitocy przejeżdża swoją maszyną po pewnym fragmencie jezdni. Maszyna maluje białe fragmenty jezdni na czerwono, a czerwone na biało. Bitocy rozważa poszczególne fragmenty jezdni zastanawiając się, ile fragmentów jest w tej chwili pomalowanych na biało.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby n i m (1 < n < 10⁹, 1 < m < 500 000) oznaczające odpowiednio: szerokość jezdni w mikrobajtometrach (µBm) oraz ilość wydarzeń. W następnych m liniach są opisy kolejnych zdarzeń. Opis takowego składa się ze znaku c ∈ {'*', '?'} oraz liczb a, b (1 < a < b < n). c = '*' oznacza, że Bitocy przejechał maszyną od a µBm do b µBm jezdni przemalowując wszystkie napotkane kolory, natomiast '?' to pytanie Bitocego o liczbę µBm pomalowanych na biało od a µBm do b µBm jezdni włącznie.

Wyjście

Na wyjście wypisz odpowiedzi na kolejne zapytania Bitocego, po jednej w linii.

Przykład

Dla danych

10 8
? 1 10
* 2 9
? 1 5
* 7 10
* 4 8
? 3 9
* 2 4
? 1 10

Poprawnym wynikiem jest:

10
1
4
6